/*
 * SPDX-FileCopyrightText: 2023 UnionTech Software Technology Co., Ltd.
 *
 * SPDX-License-Identifier: MulanPSL-2.0
 */
#![allow(
    dead_code,
    mutable_transmutes,
    non_camel_case_types,
    non_snake_case,
    non_upper_case_globals,
    unused_assignments,
    clippy::unnecessary_unwrap,
    unused_mut
)]
use crate::common::*;
extern "C" {
    fn malloc(_: libc::c_ulong) -> *mut libc::c_void;
    fn free(_: *mut libc::c_void);
    fn sudo_debug_printf2_v1(
        func: *const libc::c_char,
        file: *const libc::c_char,
        line: libc::c_int,
        level: libc::c_int,
        fmt: *const libc::c_char,
        _: ...
    );
    static mut sudoers_subsystem_ids: [libc::c_uint; 0];
}

pub type rbtraversal = libc::c_uint;
pub const postorder: rbtraversal = 2;
pub const inorder: rbtraversal = 1;
pub const preorder: rbtraversal = 0;

#[macro_export]
macro_rules! rbfirst {
    ($t:expr) => {
        (($t).root.left)
    };
}
#[macro_export]
macro_rules! rbroot {
    ($t:expr) => {
        (&mut ($t).root)
    };
}
#[macro_export]
macro_rules! rbnil {
    ($t:expr) => {
        (&mut ($t).nil)
    };
}
/*
 * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
 *
 * A red-black tree is a binary search tree where each node has a color
 * attribute, the value of which is either red or black.  Essentially, it
 * is just a convenient way to express a 2-3-4 binary search tree where
 * the color indicates whether the node is part of a 3-node or a 4-node.
 * In addition to the ordinary requirements imposed on binary search
 * trees, we make the following additional requirements of any valid
 * red-black tree:
 *  1) Every node is either red or black.
 *  2) The root is black.
 *  3) All leaves are black.
 *  4) Both children of each red node are black.
 *  5) The paths from each leaf up to the root each contain the same
 *     number of black nodes.
 */

/*
 * Create a red black tree struct using the specified compare routine.
 * Allocates and returns the initialized (empty) tree or NULL if
 * memory cannot be allocated.
 */
#[no_mangle]
pub fn rbcreate(
    mut compar: Option<
        unsafe extern "C" fn(*const libc::c_void, *const libc::c_void) -> libc::c_int,
    >,
) -> *mut rbtree {
    let mut tree: *mut rbtree = std::ptr::null_mut::<rbtree>();
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        tree = malloc(::core::mem::size_of::<rbtree>() as libc::c_ulong) as *mut rbtree;
        if tree.is_null() {
            sudo_debug_printf!(
                SUDO_DEBUG_ERROR | SUDO_DEBUG_LINENO,
                b"unable to allocate memory\0" as *const u8 as *const libc::c_char
            );
            debug_return_ptr!(std::ptr::null_mut::<rbtree>());
        }

        (*tree).compar = compar;

        /*
         * We use a self-referencing sentinel node called nil to simplify the
         * code by avoiding the need to check for NULL pointers.
         */
        (*tree).nil.parent = &mut (*tree).nil;
        (*tree).nil.right = (*tree).nil.parent;
        (*tree).nil.left = (*tree).nil.right;
        (*tree).nil.color = black;
        (*tree).nil.data = std::ptr::null_mut::<libc::c_void>();

        /*
         * Similarly, the fake root node keeps us from having to worry
         * about splitting the root.
         */
        (*tree).root.parent = &mut (*tree).nil;
        (*tree).root.right = (*tree).root.parent;
        (*tree).root.left = (*tree).root.right;
        (*tree).root.color = black;
        (*tree).root.data = std::ptr::null_mut::<libc::c_void>();

        debug_return_ptr!(tree);
    } //unsafe
}

/*
 * Perform a left rotation starting at node.
 */
fn rotate_left(mut tree: *mut rbtree, mut node: *mut rbnode) {
    let mut child: *mut rbnode = std::ptr::null_mut::<rbnode>();
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        child = (*node).right;
        (*node).right = (*child).left;

        if (*child).left != rbnil!(*tree) as *mut rbnode {
            (*(*child).left).parent = node;
        }

        (*child).parent = (*node).parent;
        if node == (*(*node).parent).left {
            (*(*node).parent).left = child;
        } else {
            (*(*node).parent).right = child;
        }
        (*child).left = node;
        (*node).parent = child;

        debug_return!();
    } //unsafe
}

/*
 * Perform a right rotation starting at node.
 */
fn rotate_right(mut tree: *mut rbtree, mut node: *mut rbnode) {
    let mut child: *mut rbnode = std::ptr::null_mut::<rbnode>();
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        child = (*node).left;
        (*node).left = (*child).right;

        if (*child).right != rbnil!(*tree) as *mut rbnode {
            (*(*child).right).parent = node;
        }
        (*child).parent = (*node).parent;

        if node == (*(*node).parent).left {
            (*(*node).parent).left = child;
        } else {
            (*(*node).parent).right = child;
        }
        (*child).right = node;
        (*node).parent = child;

        debug_return!();
    } //unsafe
}

/*
 * Insert data pointer into a redblack tree.
 * Returns a 0 on success, 1 if a node matching "data" already exists
 * (filling in "existing" if not NULL), or -1 on malloc() failure.
 */
#[no_mangle]
pub fn rbinsert(
    mut tree: *mut rbtree,
    mut data: *mut libc::c_void,
    mut existing: *mut *mut rbnode,
) -> libc::c_int {
    unsafe {
        let mut node: *mut rbnode = rbfirst!(*tree);
        let mut parent: *mut rbnode = rbroot!(*tree);
        let mut res: libc::c_int = 0;
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        /* Find correct insertion point. */
        while node != rbnil!(*tree) as *mut rbnode {
            parent = node;
            res = ((*tree).compar).expect("non-null function pointer")(data, (*node).data);
            /*if res == 0 as libc::c_int {
                if !existing.is_null() {
                    *existing = node;
                    debug_return_int!(1);
                }
            }*/

            if res == 0 as libc::c_int && !existing.is_null() {
                *existing = node;
                debug_return_int!(1);
            }

            node = if res < 0 as libc::c_int {
                (*node).left
            } else {
                (*node).right
            };
        }

        node = malloc(::core::mem::size_of::<rbnode>() as libc::c_ulong) as *mut rbnode;
        if node.is_null() {
            sudo_debug_printf!(
                SUDO_DEBUG_ERROR | SUDO_DEBUG_LINENO,
                b"unable to allocate memory\0" as *const u8 as *const libc::c_char
            );
            debug_return_int!(-(1 as libc::c_int));
        }
        (*node).data = data;
        (*node).right = rbnil!(*tree);
        (*node).left = (*node).right;
        (*node).parent = parent;
        if parent == rbroot!(*tree) as *mut rbnode
            || ((*tree).compar).expect("non-null function pointer")(data, (*parent).data)
                < 0 as libc::c_int
        {
            (*parent).left = node;
        } else {
            (*parent).right = node;
        }
        (*node).color = red;

        /*
         * If the parent node is black we are all set, if it is red we have
         * the following possible cases to deal with.  We iterate through
         * the rest of the tree to make sure none of the required properties
         * is violated.
         *
         *	1) The uncle is red.  We repaint both the parent and uncle black
         *     and repaint the grandparent node red.
         *
         *  2) The uncle is black and the new node is the right child of its
         *     parent, and the parent in turn is the left child of its parent.
         *     We do a left rotation to switch the roles of the parent and
         *     child, relying on further iterations to fixup the old parent.
         *
         *  3) The uncle is black and the new node is the left child of its
         *     parent, and the parent in turn is the left child of its parent.
         *     We switch the colors of the parent and grandparent and perform
         *     a right rotation around the grandparent.  This makes the former
         *     parent the parent of the new node and the former grandparent.
         *
         * Note that because we use a sentinel for the root node we never
         * need to worry about replacing the root.
         */
        while (*(*node).parent).color as libc::c_uint == red as libc::c_uint {
            let mut uncle: *mut rbnode = std::ptr::null_mut::<rbnode>();
            if (*node).parent == (*(*(*node).parent).parent).left {
                uncle = (*(*(*node).parent).parent).right;
                if (*uncle).color as libc::c_uint == red as libc::c_uint {
                    (*(*node).parent).color = black;
                    (*uncle).color = black;
                    (*(*(*node).parent).parent).color = red;
                    node = (*(*node).parent).parent;
                } else
                /* if (uncle->color == black) */
                {
                    if node == (*(*node).parent).right {
                        node = (*node).parent;
                        rotate_left(tree, node);
                    }
                    (*(*node).parent).color = black;
                    (*(*(*node).parent).parent).color = red;
                    rotate_right(tree, (*(*node).parent).parent);
                }
            } else {
                /* if (node->parent == node->parent->parent->right) */
                uncle = (*(*(*node).parent).parent).left;
                if (*uncle).color as libc::c_uint == red as libc::c_int as libc::c_uint {
                    (*(*node).parent).color = black;
                    (*uncle).color = black;
                    (*(*(*node).parent).parent).color = red;
                    node = (*(*node).parent).parent;
                } else
                /* if (uncle->color == black) */
                {
                    if node == (*(*node).parent).left {
                        node = (*node).parent;
                        rotate_right(tree, node);
                    }
                    (*(*node).parent).color = black;
                    (*(*(*node).parent).parent).color = red;
                    rotate_left(tree, (*(*node).parent).parent);
                }
            }
        }
        (*rbfirst!(*tree)).color = black; /* first node is always black */
        debug_return_int!(0);
    } //unsafe
}

/*
 * Look for a node matching key in tree.
 * Returns a pointer to the node if found, else NULL.
 */
#[no_mangle]
pub fn rbfind(mut tree: *mut rbtree, mut key: *mut libc::c_void) -> *mut rbnode {
    unsafe {
        let mut node: *mut rbnode = rbfirst!(*tree);
        let mut res: libc::c_int = 0;
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        while node != rbnil!(*tree) as *mut rbnode {
            res = ((*tree).compar).expect("non-null function pointer")(key, (*node).data);
            if res == 0 as libc::c_int {
                debug_return_ptr!(node);
            }
            node = if res < 0 as libc::c_int {
                (*node).left
            } else {
                (*node).right
            };
        }
        debug_return_ptr!(std::ptr::null_mut::<rbnode>());
    } //unsafe
}

/*
 * Call func() for each node, passing it the node data and a cookie;
 * If func() returns non-zero for a node, the traversal stops and the
 * error value is returned.  Returns 0 on successful traversal.
 */
#[no_mangle]
pub fn rbapply_node(
    mut tree: *mut rbtree,
    mut node: *mut rbnode,
    mut func: Option<unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> libc::c_int>,
    mut cookie: *mut libc::c_void,
    mut order: rbtraversal,
) -> libc::c_int {
    let mut error: libc::c_int = 0;
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        if node != rbnil!(*tree) as *mut rbnode {
            if order as libc::c_uint == preorder as libc::c_uint {
                error = func.expect("non-null function pointer")((*node).data, cookie);
                if error != 0 {
                    debug_return_int!(error);
                }
            }
            error = rbapply_node(tree, (*node).left, func, cookie, order);
            if error != 0 {
                debug_return_int!(error);
            }
            if order as libc::c_uint == inorder as libc::c_uint {
                error = func.expect("non-null function pointer")((*node).data, cookie);
                if error != 0 {
                    debug_return_int!(error);
                }
            }
            error = rbapply_node(tree, (*node).right, func, cookie, order);
            if error != 0 {
                debug_return_int!(error);
            }
            if order as libc::c_uint == postorder as libc::c_uint {
                error = func.expect("non-null function pointer")((*node).data, cookie);
                if error != 0 {
                    debug_return_int!(error);
                }
            }
        }

        debug_return_int!(0);
    } //unsafe
}

/*
 * Returns the successor of node, or nil if there is none.
 */
fn rbsuccessor(mut tree: *mut rbtree, mut node: *mut rbnode) -> *mut rbnode {
    let mut succ: *mut rbnode = std::ptr::null_mut::<rbnode>();
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        succ = (*node).right;
        if succ != rbnil!(*tree) as *mut rbnode {
            while (*succ).left != rbnil!(*tree) as *mut rbnode {
                succ = (*succ).left;
            }
        } else {
            /* No right child, move up until we find it or hit the root */
            succ = (*node).parent;
            while node == (*succ).right {
                node = succ;
                succ = (*succ).parent;
            }
            if succ == rbroot!(*tree) as *mut rbnode {
                succ = rbnil!(*tree);
            }
        }
        debug_return_ptr!(succ);
    } //unsafe
}

/*
 * Recursive portion of rbdestroy().
 */
fn rbdestroy_int(
    mut tree: *mut rbtree,
    mut node: *mut rbnode,
    mut destroy: Option<unsafe extern "C" fn(*mut libc::c_void) -> ()>,
) {
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());
        if node != rbnil!(*tree) as *mut rbnode {
            rbdestroy_int(tree, (*node).left, destroy);
            rbdestroy_int(tree, (*node).right, destroy);
            if destroy.is_some() {
                destroy.expect("non-null function pointer")((*node).data);
            }
            free(node as *mut libc::c_void);
        }
        debug_return!();
    } //unsafe
}

/*
 * Destroy the specified tree, calling the destructor "destroy"
 * for each node and then freeing the tree itself.
 */
#[no_mangle]
pub fn rbdestroy(
    mut tree: *mut rbtree,
    mut destroy: Option<unsafe extern "C" fn(*mut libc::c_void) -> ()>,
) {
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());
        rbdestroy_int(tree, rbfirst!(*tree), destroy);
        free(tree as *mut libc::c_void);
        debug_return!();
    } //unsafe
}

/*
 * Delete node 'z' from the tree and return its data pointer.
 */
#[no_mangle]
pub fn rbdelete(mut tree: *mut rbtree, mut z: *mut rbnode) -> *mut libc::c_void {
    unsafe {
        let mut x: *mut rbnode = std::ptr::null_mut::<rbnode>();
        let mut y: *mut rbnode = std::ptr::null_mut::<rbnode>();
        let mut data: *mut libc::c_void = (*z).data;
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        if (*z).left == rbnil!(*tree) as *mut rbnode || (*z).right == rbnil!(*tree) as *mut rbnode {
            y = z;
        } else {
            y = rbsuccessor(tree, z);
        }
        x = if (*y).left == rbnil!(*tree) as *mut rbnode {
            (*y).right
        } else {
            (*y).left
        };

        (*x).parent = (*y).parent;
        if (*x).parent == rbroot!(*tree) as *mut rbnode {
            rbfirst!(*tree) = x;
        } else if y == (*(*y).parent).left {
            (*(*y).parent).left = x;
        } else {
            (*(*y).parent).right = x;
        }
        if (*y).color as libc::c_uint == black as libc::c_int as libc::c_uint {
            rbrepair(tree, x);
        }
        if y != z {
            (*y).left = (*z).left;
            (*y).right = (*z).right;
            (*y).parent = (*z).parent;
            (*y).color = (*z).color;
            (*(*z).right).parent = y;
            (*(*z).left).parent = (*(*z).right).parent;
            if z == (*(*z).parent).left {
                (*(*z).parent).left = y;
            } else {
                (*(*z).parent).right = y;
            }
        }
        free(z as *mut libc::c_void);

        debug_return_ptr!(data);
    } //unsafe
}

/*
 * Repair the tree after a node has been deleted by rotating and repainting
 * colors to restore the 4 properties inherent in red-black trees.
 */
fn rbrepair(mut tree: *mut rbtree, mut node: *mut rbnode) {
    let mut sibling: *mut rbnode = std::ptr::null_mut::<rbnode>();
    unsafe {
        debug_decl!(SUDOERS_DEBUG_RBTREE!());

        while (*node).color as libc::c_uint == black as libc::c_uint && node != rbfirst!(*tree) {
            if node == (*(*node).parent).left {
                sibling = (*(*node).parent).right;
                if (*sibling).color as libc::c_uint == red as libc::c_uint {
                    (*sibling).color = black;
                    (*(*node).parent).color = red;
                    rotate_left(tree, (*node).parent);
                    sibling = (*(*node).parent).right;
                }
                if (*(*sibling).right).color as libc::c_uint == black as libc::c_uint
                    && (*(*sibling).left).color as libc::c_uint == black as libc::c_uint
                {
                    (*sibling).color = red;
                    node = (*node).parent;
                } else {
                    if (*(*sibling).right).color as libc::c_uint == black as libc::c_uint {
                        (*(*sibling).left).color = black;
                        (*sibling).color = red;
                        rotate_right(tree, sibling);
                        sibling = (*(*node).parent).right;
                    }
                    (*sibling).color = (*(*node).parent).color;
                    (*(*node).parent).color = black;
                    (*(*sibling).right).color = black;
                    rotate_left(tree, (*node).parent);
                    node = rbfirst!(*tree); /* exit loop */
                }
            } else {
                /* if (node == node->parent->right) */
                sibling = (*(*node).parent).left;
                if (*sibling).color as libc::c_uint == red as libc::c_uint {
                    (*sibling).color = black;
                    (*(*node).parent).color = red;
                    rotate_right(tree, (*node).parent);
                    sibling = (*(*node).parent).left;
                }
                if (*(*sibling).right).color as libc::c_uint == black as libc::c_uint
                    && (*(*sibling).left).color as libc::c_uint == black as libc::c_uint
                {
                    (*sibling).color = red;
                    node = (*node).parent;
                } else {
                    if (*(*sibling).left).color as libc::c_uint == black as libc::c_uint {
                        (*(*sibling).right).color = black;
                        (*sibling).color = red;
                        rotate_left(tree, sibling);
                        sibling = (*(*node).parent).left;
                    }
                    (*sibling).color = (*(*node).parent).color;
                    (*(*node).parent).color = black;
                    (*(*sibling).left).color = black;
                    rotate_right(tree, (*node).parent);
                    node = rbfirst!(*tree); /* exit loop */
                }
            }
        }
        (*node).color = black;

        debug_return!();
    } //unsafe
}
